/*
 * @lc app=leetcode.cn id=101 lang=csharp
 *
 * [101] 对称二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool IsSymmetric(TreeNode root) {
        // 递归 return Check(root.left, root.right);
        
        // 迭代
        if(root.left == null && root.right == null) return true;
        if(root.left == null ^ root.right == null) return false;
        TreeNode left ;
        TreeNode right ;
        var queueL = new Queue<TreeNode>();
        var queueR = new Queue<TreeNode>();
        
        queueL.Enqueue(root.left);
        queueR.Enqueue(root.right);
        
        while(queueL.Count > 0 && queueR.Count > 0)
        {
            left = queueL.Dequeue();
            right = queueR.Dequeue();

            if(left.val != right.val) return false;
            TreeNode lLeft = left.left, lRight = left.right, rLeft = right.left, rRight = right.right;
            if((lLeft == null ^ rRight == null) || (lRight == null ^ rLeft == null)) return false;
            
            if(lLeft != null)
            {
                queueL.Enqueue(lLeft);
            }
            if(lRight != null)
            {
                queueL.Enqueue(lRight);
            }
            if(rRight != null)
            {
                queueR.Enqueue(rRight);
            }
            if(rLeft != null)
            {
                queueR.Enqueue(rLeft);
            }
        }
        return queueL.Count == 0 && queueR.Count == 0;
    }
    
    // 递归
    private bool Check(TreeNode node1, TreeNode node2)
    {
        if(node1 == null && node2 == null) return true;
        if(node1 != null && node2 != null)
        {
            if(node1.val != node2.val) return false;
            return Check(node1.left, node2.right) && Check(node1.right, node2.left);
        }
        return false;
    }
}
// @lc code=end

